

//import object4.package7.Person;

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class LinkedListProblem {
    public ListNode removeElements(ListNode head, int val) {
        // 1. 判定链表是否是空的.
        if (head == null) {
            return null;
        }
        // 2. 遍历链表, 找到每一个值为 val 的节点. 从 head 之后的元素开始遍历.
        ListNode prev = head;
        ListNode cur = head.next;

        while (cur != null) {
            if (cur.val == val) {
                // 触发删除操作, 把 cur 给删掉.
                prev.next = cur.next;
                // 删除 cur 位置的节点之后, 需要移动 cur 指向下一个位置.
                cur = prev.next;
            } else {
                // 没有触发删除.
                // 移动 prev 和 cur 的指向
                prev = cur;
                cur = cur.next;
            }
        }

        // 3. 最后判定头结点的删除情况
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    public ListNode reverseList(ListNode head) {
        // 1. 判定链表为空
        if (head == null) {
            return null;
        }
        // 2. 如果链表只有一个节点, 不需要翻转的.
        if (head.next == null) {
            return head;
        }
        // 3. 处理一般情况.
        ListNode newHead = null;
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = cur.next;
        while (cur != null) {
            // 每次循环, 都需要先把 next 的位置记录下来, 再进行后续修改.
            next = cur.next;

            // 如果 next 已经是 null, 说明 cur 就是最后一个节点. 让这个节点作为新的头节点.
            if (next == null) {
                newHead = cur;
            }

            // 进行翻转操作.
            cur.next = prev;

            // 更新 prev 和 cur 的指向.
            prev = cur;
            cur = next;
        }
        return newHead;
    }

    public ListNode middleNode(ListNode head) {
        // 1. 判定链表为空
        if (head == null) {
            return null;
        }
        // 2. 求链表的长度.
        int size = size(head);
        // 3. 求出 size/2 的位置.
        int mid = size / 2;
        // 4. 从 head 出发, 走 mid 步就可以了.
        ListNode cur = head;
        for (int i = 0; i < mid; i++) {
            cur = cur.next;
        }
        return cur;
    }

    public int kthToLast(ListNode head, int k) {
        // 1. 判定链表为空, 判定 k 有效.
        if (head == null) {
            // 此处正常来说是要返回非法的值.
            // 要么返回 null
            // 要么是抛出异常.
            // 但是这两个做法在 OJ 中是不行的.
            // 实在没有别的非法值了, 就返回 0.
            return 0;
        }
        // 2. 计算整个链表的长度.
        int size = size(head);
        if (k <= 0 || k > size(head)) {
            // 注意条件的边界, 要不要写 == , 需要代入数字判定.
            // k == 0 不行, 约定 k 必须从 1 开始 (题目的例子中给定隐式条件)
            // k == size 认为是可以的. 刚才数了一下, 长度为 5 的链表, 头节点元素, 倒数第 5 个.
            return 0;
        }

        // 3. 根据 k 和长度计算出要走的步数 (size - k)
        int step = size - k;

        // 4. 从 head 出发, 走 size - k 步, 就行了.
        ListNode cur = head;
        for (int i = 0; i < step; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1. 判定链表为空
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 2. 准备两个引用指向两个链表.
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        // 3. 准备一个新的链表, 用于存放合并后的结果.
        //    同时也保存链表的尾巴. 后续都是尾插. 记录尾巴, 比较方便进行尾插的.
        //    此处如果使用 "带有傀儡节点" 的方式来实现尾插, 后续会更简单.
        ListNode newHead = new ListNode(0);
        ListNode newTail = newHead;
        // 4. 进入循环, 开始合并.
        while (cur1 != null && cur2 != null) {
            // 判定这两个引用较小的值.
            if (cur1.val < cur2.val) {
                // cur1 比较小, 插入到 newTail 之后.
                // 结果链表不为空链表. 尾插.
                newTail.next = cur1;
                // 插入完毕之后, 让 newTail 指向新的尾巴.
                newTail = cur1;
                // 更新 cur1 指向下一个节点.
                cur1 = cur1.next;
            } else {
                // cur2 比较小, 插入到 newTail 之后.
                newTail.next = cur2;
                newTail = cur2;
                // 更新 cur2 指向下一个节点.
                cur2 = cur2.next;
            }
        }
        // 5. 上述循环完毕, 意味着 cur1 或者 cur2 有一个已经遍历完了.
        //    只需要把剩余的节点, 挂到新链表末尾即可.
        if (cur1 != null) {
            // cur1 还有剩余, 挂到 newTail 之后.
            newTail.next = cur1;
        }
        if (cur2 != null) {
            // cur2 还有剩余, 挂到 newTail 之后.
            newTail.next = cur2;
        }
        // 6. 返回合并后的链表. newHead 指向的是傀儡节点. 真正的头结点是 newHead.next
        return newHead.next;
    }

    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        if (pHead.next == null) {
            // 链表只有一个节点, 得到的结果还是本身.
            return pHead;
        }
        // 针对一般情况, 先创建两个链表.
        // 由于接下来都是尾插, 为了方便, 直接创建 tail 指向尾部节点, 并且创建傀儡节点, 简化逻辑.
        ListNode smallHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode largeTail = largeHead;
        // 遍历链表
        for (ListNode cur = pHead; cur != null; cur = cur.next) {
            if (cur.val < x) {
                // 把 cur 尾插到 smallTail 之后.
                smallTail.next = cur;
                smallTail = cur;
            } else {
                // 把 cur 尾插到 largeTail 之后.
                largeTail.next = cur;
                largeTail = cur;
            }
        }
        // 最后把 large 这个链表追加到 small 之后.
        // 把 large 链表的头结点(傀儡之后的节点), 使用 smallTail 的 next 指向.
        smallTail.next = largeHead.next;
        // 稳妥起见, 把 largeTail 的 next 指向 null. 避免出现 由于 largeTail next 不为空导致的链表出错.
        largeTail.next = null;
        return smallHead.next;
    }

    // 空间复杂度 O(N) 的版本.
    public boolean chkPalindrome2(ListNode A) {
        if (A == null) {
            // 空链表, 视为回文
            return true;
        }
        if (A.next == null) {
            // 只有一个节点, 也视为回文
            return true;
        }
        // 1. 把链表复制一份
        ListNode newHead = new ListNode(0);
        ListNode newTail = newHead;
        for (ListNode cur = A; cur != null; cur = cur.next) {
            ListNode newNode = new ListNode(cur.val);
            newTail.next = newNode;
            newTail = newNode;
        }
        // 傀儡节点不再使用了.
        newHead = newHead.next;

        // 2. 把复制的链表逆置
        ListNode prev = null;
        ListNode cur = newHead;
        while (cur != null) {
            ListNode next = cur.next;
            if (next == null) {
                newHead = cur;
            }
            // 关键操作
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // 3. 比较两个链表是否相同
        ListNode cur1 = A;
        ListNode cur2 = newHead;
        while (cur1 != null && cur2 != null) {
            if (cur1.val != cur2.val) {
                // 出现不相等的情况, 一定不是回文.
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if (cur1 == null && cur2 == null) {
            // 两个链表同时遍历完, 长度相同, 就是回文
            return true;
        }
        // 两个链表长度不同, 不是回文.
        return false;
    }

    // 空间复杂度 O(1) 的版本.
    public boolean chkPalindrome(ListNode A) {
        if (A == null) {
            return true;
        }
        if (A.next == null) {
            return true;
        }
        // 1. 找到链表中间节点.
        int size = size(A);
        int step = size / 2;
        ListNode B = A;
        for (int i = 0; i < step; i++) {
            B = B.next;
        }
        // 此时 B 指向的就是中间节点了.

        // 2. 针对 B 这个链表进行逆置.
        ListNode prev = null;
        ListNode cur = B;
        while (cur != null) {
            ListNode next = cur.next;
            if (next == null) {
                // cur 就是新的头节点.
                B = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // 3. 比较 A 和 B 两个链表是否相同.
        ListNode cur1 = A;
        ListNode cur2 = B;
        while (cur1 != null && cur2 != null) {
            if (cur1.val != cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        // 不去考虑长度问题了. 如果节点是偶数个, 此时 A 的长度就是会比 B 多一个.
        return true;
    }

    public int size(ListNode head) {
        int size = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            size++;
        }
        return size;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 判定空的情况先放一放, 先往后写, 再回头看是否需要判空
        // 1. 求两个链表的长度.
        int sizeA = size(headA);
        int sizeB = size(headB);
        // 2. 让长的链表的引用先往后走 长度差值 步.
        ListNode curA = headA;
        ListNode curB = headB;
        if (sizeA > sizeB) {
            // A 链表先走, sizeA - sizeB 步.
            for (int i = 0; i < sizeA - sizeB; i++) {
                curA = curA.next;
            }
        } else {
            // B 链表先走, sizeB - sizeA 步.
            for (int i = 0; i < sizeB - sizeA; i++) {
                curB = curB.next;
            }
        }
        // 3. 再让两个引用同时出发, 往后各自走一步, 看什么时候两个引用指向同一个节点 (相遇), 此时的这个节点就是交点.
        while (curA != null && curB != null) {
            if (curA == curB) {
                // 两个引用相遇了. 此时得到的这个节点就是链表的交点.
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        // 4. 如果遍历结束, 两个引用也没有相遇, 说明链表不相交.
        return null;
    }

    public boolean hasCycle2(ListNode head) {
        // 朴素的做法: 使用 List 记录遍历过程中的每个节点.
        // 每次取到一个节点, 都先判定是否已经在 List 中出现过.
        // 如果出现过, 就是带环的.
        if (head == null) {
            return false;
        }
        List<ListNode> list = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (list.contains(cur)) {
                // 带环了.
                return true;
            } else {
                list.add(cur);
            }
        }
        return false;
    }

    public boolean hasCycle(ListNode head) {
        // 使用双引用, 一个快引用, 一个慢引用.
        // 初始情况下, 两个引用都指向 head.
        // 让快引用一次走两步, 慢引用一次走一步.
        // 判定是否会重合. 如果重合就是带环了.
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        // 没有出发上述 return true, 反而是触发了 fast 为 null 或者 fast.next 为 null.
        // 此时链表无环的.
        return false;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        // 1. 使用快慢指针, 找到相遇位置. 如果不相遇, 说明无环.
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 循环结束, 需要判定, 是因为 fast 和 slow 重合, 结束循环的, 还是因为 fast 为 null 结束循环的.
        if (fast == null || fast.next == null) {
            // 无环的情况, fast 已经到末尾了.
            return null;
        }
        // 2. 设置一个 cur1 , 从 head 出发, 设置 cur2 从交汇位置出发. 两个引用同时往前走.
        //    两个引用重合的位置, 就是环的入口点.
        ListNode cur1 = head;
        ListNode cur2 = slow;
        // 这里的循环一定不会死循环的. 通过数学公式已经证明了, cur1 和 cur2 是必定会相遇.
        // 而且相遇的位置就是环的入口.
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        // 循环结束, 说明 cur1 和 cur2 相遇了.
        return cur1;
    }

    public static void main(String[] args) {
        ListNode head = null;
        LinkedListProblem solution = new LinkedListProblem();
        solution.reverseList(head);
    }
}
